# coding:utf8
# author:WHY
# time:2016-05-22

class Scanner:
	# lexical
	def __init__(self, sorce, begin):
		self.sorce = sorce			# 源代码
		self.row = 1                # 当前源代码位置，行
		self.col = 1                # 当前源代码位置，列
		self.nfa = {}               # 不确定有穷自动机
		self.vt = set()				# 终结符
		self.vn = set()				# 非终结符
		self.dfa = {}               # 确定的有穷自动机
		self.currect = 0			# 当前字符位置
		self.buffer = ""            # 缓冲区
		self.nearestAccept = 0      # 最近可被接受状态
		self.state = 0              # 当前状态
		self.nfaBegin = begin		# NFA的起点
		self.keyword = []			# 关键字
		
	def makeNFA(self, grammar, endName):
		# 生成NFA
		if endName is None:
			endName = "test"
		for line in grammar:
			if len(line) <2:
				continue
				
			self.vn.add(line[0])		# 统计终极符和非终结符
			self.vt.add(line[1])
			
			if line[0] not in self.nfa.keys():
				self.nfa.setdefault(line[0], {})
				self.nfa[line[0]].setdefault('edge', {})
				
			if line[1] not in self.nfa[line[0]].keys():
				self.nfa[line[0]]['edge'].setdefault(line[1], [])
				self.nfa[line[0]].setdefault('isEndNode', False)	# 判断是否是可终止状态
			
			if len(line) == 3:
				self.vn.add(line[2])
				self.nfa[line[0]]['edge'][line[1]].append(line[2])
			else:
				self.nfa[line[0]]['isEndNode'] = True
				if endName not in self.nfa[line[0]].keys():
					self.nfa[line[0]].setdefault('endName', endName)	# 标识符，常量等等
				
	def NFAtoDFA(self):
		# 生成DFA
		tempState = {
			'isVisit':False,
			'isEndNode':False,
			'data':tuple(set([self.nfaBegin]))
		}
		stateSet = {}
		self.dfaBegin = hash(tempState['data'])
		stateSet.setdefault(self.dfaBegin, tempState)
		
		flag = True
		while flag:
			flag = False
			for currentID,currentState in stateSet.items():
				if currentState['isVisit'] == False:
					currentState['isVisit'] = True
					
					if currentID not in self.dfa.keys():
							self.dfa.setdefault(currentID, {})
							self.dfa[currentID] = {
								'edge': {},
								'isEndNode': currentState['isEndNode'],
								'data':currentState['data']
							}
							if 'endName' in currentState.keys():
								self.dfa[currentID].setdefault('endName',currentState['endName'])
								
					for vt in self.vt:
						newState = {
							'isVisit':False,
							'isEndNode':False,
							'data':set()
						}
						(isEndNode, endName, moveSet) = self.move(currentState, vt)
						
						if isEndNode :
							self.dfa[currentID]['isEndNode'] = True
							self.dfa[currentID]['endName'] = endName
							
						newState['data'] = newState['data'].union(moveSet)
						if len(newState['data']) == 0 :
							continue
						newState['data'] = tuple(newState['data'])
						id = hash(newState['data'])
						
						if id not in stateSet.keys():
							stateSet.setdefault(id, newState)
							flag = True
							
						
						self.dfa[currentID]['edge'].setdefault(vt, id)
				
	def move(self, State, vt):
		# 进行move操作
		tempState = set()
		endNode = False
		endName = ''
		if 'identifier' in State['data']:
			pass
		for vn in State['data']:
			if vn != '###':
				if vt in self.nfa[vn]['edge'].keys():
					tempState = tempState.union(set(self.nfa[vn]['edge'][vt]))
				if '&' in self.nfa[vn]['edge'].keys():
					endNode = True
					endName = self.nfa[vn]['endName']
		return (endNode, endName, tempState)
		
	def getToken(self):
		self.preprocess()
		self.beginRow = self.row
		self.beginCol = self.col
		stop = False
		self.nearestAccept = 0
		self.buffer = ''
		self.state = self.dfaBegin
		self.nearestState = 0
		length = len(self.sorce)
		
		while not stop:
			if self.currect == length:
				if self.nearestAccept != 0:
					token = self.submitToken()
				else:
					token = ''
				self.state = 'EOF'
				stop = True
				continue
			ch = self.sorce[self.currect]
			if ch.isspace():
				ch = 'space'			# 用space代替空白符
			if ch in self.dfa[self.state]['edge'].keys():
				self.buffer += self.sorce[self.currect]
				self.state = self.dfa[self.state]['edge'][ch]
				if self.dfa[self.state]['isEndNode']:
					self.nearestAccept = len(self.buffer)
					self.nearestState = self.state
				self.getNextChar()
			else:
				token = self.submitToken()
				stop = True
		self.token = token
		return token
		
	def preprocess(self):
		length = len(self.sorce)
		while self.sorce[self.currect].isspace():
			self.getNextChar()
			if length <= self.currect:
				break
			
	def getTokenType(self):
		if self.nearestState != 0 and self.dfa[self.nearestState]['isEndNode']:
			if self.token.lower() in self.keyword:
				return self.token.lower()
			elif self.dfa[self.nearestState]['endName'] == '@limiter'\
				or self.dfa[self.nearestState]['endName'] == '@operator':
				return self.token
			elif self.token.lower() in self.typeList:
				return '@type-identifier'
			else:
				return self.dfa[self.nearestState]['endName']
		elif self.state == 'EOF':
			return 'EOF'
		else:
			return 'UNKNOW'
			
	def getState(self):
		return self.state
		
	def submitToken(self):
		# 提交Token
		if self.nearestAccept != 0:
			token = self.buffer[:self.nearestAccept]
			self.currect = self.currect - len(self.buffer) + self.nearestAccept
			return token
		else:
			print 'Error:\t'
			self.currect -= len(self.buffer)
			self.currect += 1
			return self.sorce[self.currect - 1]
		
	def getNextChar(self):
		if self.sorce[self.currect] == '\n':
			self.row +=1
			self.col = 0
		self.currect += 1
		self.col += 1
		
		
			
	def getRow(self):
		return self.beginRow
		
	def getCol(self):
		return self.beginCol
		
	def addKeyword(self, keyword):
		self.keyword = keyword
			
	def addType(self, typeList):
		self.typeList = typeList